#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; space ;
    print(p...) ;
}
bool S_GND ;
const int N = 205 ;
int T,n,m,MOD ;
int f[N*N],g[N*N] ;
inline int Pow(long long x,int p)
{
    long long res = 1 ; while(p)
    {
        if(p&1) res = res*x%MOD ;
        x = x*x%MOD,p >>= 1 ;
    }
    return res ;
}
inline void Add(int &x,int y)
{
    x = (x+y>=MOD)?x+y-MOD:x+y ;
}
void Solve()
{
    read(n,m),me(f,0) ;
    FOR(i,0,m,1) f[i] = 1 ;
    FOR(i,2,n,1)
    {
        g[0] = f[0] ;
        FOR(j,1,i*m,1) g[j] = f[j],Add(g[j],g[j-1]) ;
        FOR(j,0,m,1) f[j] = g[j] ;
        FOR(j,m+1,i*m,1) f[j] = g[j]-g[j-m-1]<0?g[j]-g[j-m-1]+MOD:g[j]-g[j-m-1] ;
    }
    long long res = 0 ;// FOR(i,1,n*m,1) print(f[i]) ; enter ;
    FOR(i,1,n*m,1) (res += 1ll*f[i]*f[i-1]%MOD) %= MOD,Add(f[i],f[i-1]) ;
    print(res*Pow(Pow(m+1,2*n)%MOD,MOD-2)%MOD),enter ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
	freopen("pr.in","r",stdin) ;
	freopen("pr.out","w",stdout) ;
    read(MOD,T) ; 
    while(T--) Solve() ;// cerr<<clock()/1000.0 ;
    return 0 ;
}